This invention relates generally to replication between networked servers or computers and, more particularly, relates to a method to detect partially replicated objects in a database in order to ensure that such objects are used in a consistent state in distributed database implementations.
Use of distributed computer networks to implement databases results in more responsive databases, including local updating and management in multiple master systems. Redundancy built into a distributed implementation results in a more resilient and reliable database. A database may be thought of as constituting two essential properties, viz., a collection of data objects and a set of procedures/tools/methods for locating a particular one of the data objects. The procedures/tools/methods for locating a particular data item are included in a directory or directory service. There may be more than one directory in a database, and possibly a directory service for assistance in locating the proper directory. The directory service is a namespace that aids in resolution of an identifier to a corresponding object, or even attribute, using appropriate mappings that include simple directory tables. Commercial databases typically include storage for the objects and implementations of directory services for navigating the directories describing the organization of the stored data in the database.
Databases are central to meaningful transactions on a computer regardless of whether a computer is networked or not. A file stored in an ordinary personal computer hard drive is, ultimately, an entry in a database accessed through a file access table having file names and a plurality of memory locations. Moreover, changes to this file may be incremental in that the entire file is not rewritten immediately, but instead, a record is made of the desired changes. If two different entities try to access and modify a typical file, traditionally only one is permitted with the other one being locked out. This is a safety feature designed to avoid inconsistent changes that may interfere with the operation of software. Commercial databases are designed for different contexts but often have similar concerns during their use by client applications.
In order to minimize the risk of service disruption and facilitate faster access, commercial databases are preferably maintained on several networked computers, playing the role of servers, which update each other""s versions. These updating operations between computers are termed replications. If a particular computer crashes, another computer takes-over. Users of the database may actually be only aware of a database-implementing network as a single entity rather than the individual components that make up the network.
A replication operation may result in the copying the entire state of a database to another database. However, this is often impractical and usually an incremental replication scheme (IRS) is implemented instead. In an IRS, changes since the last replication step, or portions thereof, are replicated to the other machine.
Generally, there are two commonly used strategies for carrying out an IRS, and there are numerous variations within each strategy. The first strategy utilizes the single-master server (SMS) model in which one of the computers is designated as the primary server (PS). One or more backup servers (BS) replicate from the PS. Changes are first made to the PS and are then propagated to the backup servers via replication. During replication between PS and BS, often a lock is placed on both to ensure that the data does not change while replication is taking place. Furthermore, the replicating components are usually unavailable for the duration of the lock. The reasons for placing a lock include the desire to avoid identifying two machines as being synchronized when one or both may change during the process for synchronization itself, with the possibility of the next incremental replication operation treating non-replicated data as already having been replicated.
The second strategy for IRS is based on networking multiple-master servers (MMS). In a multiple-master system, many servers replicate from each other, and changes may be independently made to their respective databases. This permits updates to be made locally with local management while the changes eventually are reflected in the entire network. Thus, in the MMS system there is no need for a primary server. Furthermore, a server may even restrict itself to a defined subset of the data while routing requests requiring additional data to other servers in the network.
A difficulty presented by MMS units is that changes to the database can occur, in any order, on any of the MMSs in a network. Furthermore, because many older networks utilize the single-master server model many hybrid networks may exist where the multiple master servers replicate to other multiple master servers while one of the multiple master servers emulates a primary server for the benefit of single master servers in the network. Further details about managing replication in a hybrid network are provided in the U.S. patent application Ser. No. 09/360,498, xe2x80x9cMETHOD AND SYSTEM FOR REPLICATION IN A HYBRID NETWORK,xe2x80x9d filed on Jul. 26, 1999.
Many implementations of MMS networks are based on the multi-master loose consistency with convergence model in which a change to a replica propagates to other replicas but without any guarantees that at any given time the replicas will be consistent with each other. If no new changes are made then the system is guaranteed to converge on the same set of values. This model is attractive because it is compatible with highly distributed database implementations capable of growing to include millions of objects and thousands of replicas. In addition, the model also allows for inclusion of nodes with intermittent connectivity in the network.
Accessing inconsistent data can be a handicap for many applications. Inconsistent data among various replicas in multi-master loose consistency with convergence model is due to propagation time needed by the updates to reach the entire network. There is no known strategy for predicting the future state of a system based on such a model or even predicting when changes would be applied in the system resulting in a xe2x80x9cnondeterministic latency,xe2x80x9d which is a fact of life for applications operating in such an environment.
From the perspective of applications, which are the usual clients for database services, in a multi-master loose consistency with convergence model, there are three states that may be encountered. First is the possibility that none of the changes to a source have propagated to a destination replica resulting in a xe2x80x9cversion skew.xe2x80x9d Applications have to expect such a possibility of having consistent but stale data. Second, only some of the changes applied to a source may have propagated to a destination replica resulting in a xe2x80x9cpartial-update.xe2x80x9d An application retrieving data from the replication replica would benefit from knowing that it is a partial-update, specially, if consistency between data objects is important. Third, all of the changes applied at a source may have propagated to a destination replica resulting in a xe2x80x9cfully replicatedxe2x80x9d state.
Directory-enabled applications use directory services to store configuration information, operational instructions or other information. It is possible that multiple copies of the application may be executing on the network at the same time, and as a consequence, reading/writing to replicas of the directory service. It is possible that some directory-enabled applications may use more than one replica. Some of these applications may handle version skew should an inconsistency be detected between replicas, provided partial-updates can be ruled out.
An exemplary application, sensitive to consistency concerns, is a remote access service using the directory to store policy and profile information. The policy information is stored in one set of objects, and the profile in another object-set. When a user connects to the remote access service, the remote access service reads the policy to determine whether the user has access, and if so what profile to apply to the user""s session. Partial-update can affect the remote access service in several ways. If the policy is complex and consists of multiple objects, the remote access service might read a partially updated policy resulting in incorrect denial or granting of service to the user, inability to process the policy due to internal inconsistency, etc. If the both policy and profiles have been updated, the service might correctly process the policy but apply a stale profile, because the policy objects have replicated but the profile objects have not. If the profile is complex and consists of multiple objects, the service might correctly process the policy but apply a partially updated profile because the policy objects have replicated but only some of the profile objects have done so.
In addition, detection of unauthorized partial-updates is important in many contexts. If making unauthorized changes results in a partial-update, the detection of the partial-update would provide protection to applications requiring secure data.
In view of the foregoing, in accordance with this invention, a method and system are provided for detecting partially updated data object-sets. Data objects required to be consistent with each other are organized as a contiguous sub-tree in a database to form an object-set. The root node of this sub-tree stores a consistency-identifier, preferably a globally unique identifier (GUID), which is generated anew each time the object-set is changed to another updated consistent object-set. The root node also stores the value of a function of the count of children of the root node. A user accessing data in this sub-tree has available methods for creating an object-set, validating an object-set and invalidating an object-set by checking if the number of children with the same consistency-identifier matches the number of children recorded in the root node. Other functions may be constructed to provide combinations or extensions of similar functions.
An operation for reading data invokes the object-set validating method, which indicates if the object-set sub-tree is partially updated. An operation for writing, i.e., changing the object-set, invokes the object-set invalidating method so that subsequent attempts to read from the object-set reveal that an update is being made. The write operation terminates after invoking the create_object_set method to make the object-set valid.
This strategy is also compatible with and useful in detecting unauthorized access or modifications to an object-set by adding digital signatures, (and, optionally, encryption) to the entries and providing a user interface between a client and the server to facilitate authentication by standard protocols. In some versions, modifications by an unauthorized source could result in the object set being marked as a partial update for an extraordinary length of time.